type List<T> = {
    head: T,
    tail: List<T>
} | null

function toList<T>(xs: T[]): List<T> {
    if (xs.length <= 0) {
        return null
    }
    return {
        head: xs[0],
        tail: toList(xs.slice(1))
    }
}

function printList<T>(xs: List<T>) {
    while (xs !== null) {
        console.log(xs.head)
        xs = xs.tail
    }
}

// function sum<T>(xs: List<T>) {
//     if (xs === null) {
//         return 0
//     }
//     return xs.head + sum(xs.tail)
// }


type BinOp<T, S> = (elem: T) => (acc: S) => S;
const reduce = <T, S>(f: BinOp<T, S>) => (identidy: S) => (xs: List<T>): S => {
    if (xs === null) {
        return identidy
    }
    return f(xs.head)(reduce(f)(identidy)(xs.tail))
}

const add = (x: number) => (y: number): number => {
    return x + y
}

let xs = toList([1, 2, 3])
const sum = reduce(add)(0)
console.log(sum(xs))



console.log("============")



const multiply = (x: number) => (y: number): number => {
    return x * y
}
const product = reduce(multiply)(1)

const or = (x: boolean) => (y: boolean): boolean => {
    return x || y
}
const anyTrue = reduce(or)(false)

const and = (x: boolean) => (y: boolean): boolean => {
    return x && y
}
const allTrue = reduce(and)(true)

const cons = <T>(x: T) => (ys: List<T>): List<T> => {
    return {
        head: x,
        tail: ys
    }
}
const append = reduce(cons)

printList(append(toList([3, 4]))(toList([1, 2])))



// New，所有代码已更新，需在 md 中同步一下

type MonaOp<T, S> = (x: T) => S;
const compose = <T, S, R>(f: (x: R) => S, g: (y: T) => R) => {
    return (x: T) => f(g(x))
}

const map = <T, S>(f: MonaOp<T, S>) => reduce(compose(cons, f))(null)


function double(x: number) { return 2 * x; }
const doubleAll = map(double)


// sum matrix
const sumMatrix = compose(sum, map(sum))


// TODO: ordered labelled trees

type TreeNode<T> = {
    label: T,
    subTrees: List<TreeNode<T>>
}

const reduceTree = <T, S, R>(f: BinOp<T, S>) => (g: any) => (identity: S) => (node: TreeNode<T>): S => {
    return f(node.label)(reduceTree1(f)(g)(identity)(node.subTrees))
}

const reduceTree1 = <T, S, R>(f: BinOp<T, S>) => (g: any) => (identity: S) => (subTrees: List<TreeNode<T>>): S => {
    if (subTrees === null) {
        return identity
    }
    return g(reduceTree(f)(g)(identity)(subTrees.head))
}

const sumTree = reduceTree(add)(add)(0)
let t1 = reduceTree(add)  // S = T
// T => T => T

const labels = reduceTree(cons)(append)(null)
let t2 = reduceTree(cons)  // S = List<T>
// List<T> => List<T> => List<T>


const node = <S>(e: S) => {
    return e
}
const mapTree = <T, S>(f: BinOp<T, S>) => reduceTree(compose(node, f))(cons)(null)
let t3 = <T, S>(f: BinOp<T, S>) => reduceTree(compose(node, f))
// T => List<T> => List<T>